/*
题目: 矩阵中和能被 K 整除的路径
给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果

https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k
 */
public class NumberOfPaths {
    private static final int M = (int) 1e9 + 7;
    int m, n, k;
    long src = 0;
    long[][][] memo = null;
    public int numberOfPaths(int[][] grid, int k) {
        // 记忆化搜索
        m = grid.length;
        n = grid[0].length;
        this.k = k;
        // 表示到达[m][n] 坐标且 模为 v 时的路径个数
        memo = new long[m][n][k];
        for (int i = 0; i < m; i ++)
            for (int j = 0; j < n; j ++)
                Arrays.fill(memo[i][j], -1L);

        dfs(grid, 0, 0, 0L);
        return (int) (src % M);
    }

    private long dfs(int[][] grid, int x, int y, long sum) {
        if (x < 0 || x >= m || y < 0 || y >= n) return 0;

        sum = (grid[x][y] + sum) % k;
        int mod = (int) sum;
        if (x == m - 1 && y == n - 1) {
            if (mod == 0) {
                src ++;
                return 1; // 返回一条路径
            } else {
                return 0;
            }
        }

        if (memo[x][y][mod] != -1) {
            src += memo[x][y][mod];
            return memo[x][y][mod];
        }
        memo[x][y][mod] = dfs(grid, x + 1, y, sum) + dfs(grid, x, y + 1, sum);
        return memo[x][y][mod] % M;
    }
}
